from primes import prime
from miller_rabin import is_prime

def concatNr(a,b):
    return int(str(a) + str(b))

def isInterestingPrimePair(a,b):
    return is_prime(concatNr(a,b)) and is_prime(concatNr(b,a))

def solution1():
    primeGen = prime()
    primeSets = [list() for x in xrange(5)]
    
        
    def isInterestingPrimeSet(s, p):
        return all(isInterestingPrimePair(x,p) for x in s)
    
    def addInterestingSets(dest, src, p):
        for s in src:
            if isInterestingPrimeSet(s, p):
                if 3 <= len(s):
                    print "adding", s + [p]
                dest.append(s + [p])
                if 4 <= len(s):
                    print "done"
                    exit()
        
    for p in primeGen:
        for l in range(len(primeSets), 1, -1):
            addInterestingSets(primeSets[l-1], primeSets[l-2], p)
    
        primeSets[0].append([p])

def solution2():
    D = {}
    p_gen = prime()
    p = p_gen.next() # discard 2 
    p = p_gen.next()
    D[p] = set([frozenset([p])]) # 3
    p = p_gen.next() # discard 5
    while True:
        p = p_gen.next()
        possibles = set([i for i in D.keys() if isInterestingPrimePair(p, i)])
        p_set = frozenset([p])
        gen_sets = set([p_set])
        for i in D.keys():
            if i in possibles:
                new_sets = set()
                for s in D[i]:
                    if s <= possibles:
                        sp = s | p_set
                        if len(sp) == 5:
                            return sp
                        new_sets.add(sp)
                        gen_sets.add(sp)
                D[i] |= new_sets
        D[p] = gen_sets
 
def solution3():       
    # map each n into the list of compatible numbers < n
    pmap = {}
     
    def solve_p060(size):
        for n in prime():
            sn = str(n)
            pp = []
            for p in pmap:
                if is_prime(int(sn + p)) and is_prime(int(p + sn)):
                   pp.append(p)
            pmap[sn] = set(pp)
     
            for sol in iter_sol(sn, size):
                print ', '.join(sol)
                return sum(map(int, sol))
     
    # Map every solution length in the numbers for which there is no solution
    # so much long with the number as bigger item.
    noway = {}
     
    def iter_sol(sn, length):
        """Get solutions of the proper length having sn as bigger number."""
        if length == 1:
            yield (sn,)
            return
     
        if length not in noway:
            noway[length] = set()
     
        if sn in noway[length]:
            return
     
        found = False
        for p in pmap[sn]:
            for sol in iter_sol(p, length - 1):
                for p2 in sol:
                    if p2 not in pmap[sn]:
                        break
                else:
                    yield sol + (sn,)
                    found = True
     
        if not found:
            noway[length].add(sn)
     
    #print solve_p060(4)     # 792
    print solve_p060(5)     # 26033

from timeit import Timer
print Timer('print solution3()', 'from __main__ import solution3').timeit(1)  
